<!DOCTYPE html>
<html lang="en">

<!-- Head tag -->
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="">
    <meta name="keyword" content="">
    <meta name="theme-color" content="#600090">
    <meta name="msapplication-navbutton-color" content="#600090">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="#600090">
    <link rel="shortcut icon" href="https://cdn4.iconfinder.com/data/icons/ionicons/512/icon-person-128.png">
    <link rel="alternate" type="application/atom+xml" title="菜菜莱莱" href="/atom.xml">
    <link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/animate.css/3.5.2/animate.min.css">
    <link rel="stylesheet" href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.css">
    <title>
        
        Java 8中HashMap和LinkedHashMap如何解决冲突｜极乐净土
        
    </title>

    <link rel="canonical" href="http://sy0626.gitee.io/2017/07/10/什么时候会产生冲突/">

    <!-- Bootstrap Core CSS -->
    <link rel="stylesheet" href="/css/bootstrap.min.css">

    <!-- Custom CSS -->
    <link rel="stylesheet" href="/css/blog-style.css">

    <!-- Pygments Github CSS -->
    <link rel="stylesheet" href="/css/syntax.css">
</head>

<style>

    header.intro-header {
        background-image: url('')
    }
</style>
<!-- hack iOS CSS :active style -->
<body ontouchstart="" class="animated fadeIn">
<!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top " id="nav-top" data-ispost = "true" data-istags="false
" data-ishome = "false" >
    <div class="container-fluid">
        <!-- Brand and toggle get grouped for better mobile display -->
        <div class="navbar-header page-scroll">
            <button type="button" class="navbar-toggle">
                <span class="sr-only">Toggle navigation</span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </button>
            <a class="navbar-brand animated pulse" href="/">
                <span class="brand-logo">
                    菜菜莱莱
                </span>
                's Blog
            </a>
        </div>

        <!-- Collect the nav links, forms, and other content for toggling -->
        <!-- Known Issue, found by Hux:
            <nav>'s height woule be hold on by its content.
            so, when navbar scale out, the <nav> will cover tags.
            also mask any touch event of tags, unfortunately.
        -->
        <!-- /.navbar-collapse -->
        <div id="huxblog_navbar">
            <div class="navbar-collapse">
                <ul class="nav navbar-nav navbar-right">
                    <li>
                        <a href="/">Home</a>
                    </li>
					
                    
					
					
                </ul>
            </div>
        </div>
    </div>
    <!-- /.container -->
</nav>
<script>
    // Drop Bootstarp low-performance Navbar
    // Use customize navbar with high-quality material design animation
    // in high-perf jank-free CSS3 implementation
//    var $body   = document.body;
    var $toggle = document.querySelector('.navbar-toggle');
    var $navbar = document.querySelector('#huxblog_navbar');
    var $collapse = document.querySelector('.navbar-collapse');

    $toggle.addEventListener('click', handleMagic)
    function handleMagic(e){
        if ($navbar.className.indexOf('in') > 0) {
        // CLOSE
            $navbar.className = " ";
            // wait until animation end.
            setTimeout(function(){
                // prevent frequently toggle
                if($navbar.className.indexOf('in') < 0) {
                    $collapse.style.height = "0px"
                }
            },400)
        }else{
        // OPEN
            $collapse.style.height = "auto"
            $navbar.className += " in";
        }
    }
</script>

<!-- Main Content -->

<!--only post-->


<img class="wechat-title-img"
     src="">


<style>
    
    header.intro-header {
        background-image: url('')
    }

    
</style>

<header class="intro-header">
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1 text-center">
                <div class="post-heading">
                    <h1>Java 8中HashMap和LinkedHashMap如何解决冲突</h1>
                    
                    <span class="meta">
                         作者 菜菜莱莱
                        <span>
                          日期 2017-07-10
                         </span>
                    </span>
                    <div class="tags text-center">
                        
                        <a class="tag" href="/tags/#个人学习"
                           title="个人学习">个人学习</a>
                        
                    </div>
                </div>
            </div>
        </div>
    </div>
    <div class="post-title-haojen">
        <span>
            Java 8中HashMap和LinkedHashMap如何解决冲突
        </span>
    </div>
</header>

<!-- Post Content -->
<article>
    <div class="container">
        <div class="row">
            <!-- Post Container -->
            <div class="col-lg-8 col-lg-offset-1 col-sm-9 post-container">
                <p>在Java 8 之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。为了解决在频繁冲突时hashmap性能降低的问题，Java 8中使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。在Java 8中使用常量<strong>TREEIFY_THRESHOLD</strong>来控制是否切换到平衡树来存储。目前，这个常量值是8，这意味着当有超过8个元素的索引一样时，HashMap会使用树来存储它们。这一改变是为了继续优化常用类。在Java 7中为了优化常用类对ArrayList和HashMap采用了延迟加载的机制，在有元素加入之前不会分配内存，这会减少空的链表和HashMap占用的内存。这一动态的特性使得HashMap一开始使用链表，并在冲突的元素数量超过指定值时用平衡二叉树替换链表。不过这一特性在所有基于hash table的类中并没有，例如Hashtable和WeakHashMap。目前，只有<strong>ConcurrentHashMap</strong>,<strong>LinkedHashMap</strong>和<strong>HashMap</strong>会在频繁冲突的情况下使用平衡树。</p>
<h4 id="什么时候会产生冲突"><a href="#什么时候会产生冲突" class="headerlink" title="什么时候会产生冲突"></a>什么时候会产生冲突</h4><p>HashMap中调用<strong>hashCode()</strong>方法来计算hashCode。由于在Java中两个不同的对象可能有一样的hashCode,所以不同的键可能有一样hashCode，从而导致冲突的产生。</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>HashMap在处理冲突时使用链表存储相同索引的元素。<br>从Java 8开始，HashMap，ConcurrentHashMap和LinkedHashMap在处理频繁冲突时将使用平衡树来代替链表，当同一hash桶中的元素数量超过特定的值便会由链表切换到平衡树，这会将get()方法的性能从O(n)提高到O(logn)。<br>当从链表切换到平衡树时，HashMap迭代的顺序将会改变。不过这并不会造成什么问题，因为HashMap并没有对迭代的顺序提供任何保证。<br>从Java 1中就存在的Hashtable类为了保证迭代顺序不变，即便在频繁冲突的情况下也不会使用平衡树。这一决定是为了不破坏某些较老的需要依赖于Hashtable迭代顺序的Java应用。<br>除了Hashtable之外，WeakHashMap和IdentityHashMap也不会在频繁冲突的情况下使用平衡树。<br>使用HashMap之所以会产生冲突是因为使用了键对象的hashCode()方法，而equals()和hashCode()方法不保证不同对象的hashCode是不同的。需要记住的是，相同对象的hashCode一定是相同的，但相同的hashCode不一定是相同的对象。<br>在HashTable和HashMap中，冲突的产生是由于不同对象的hashCode()方法返回了一样的值。</p>
<p>以上就是Java中HashMap如何处理冲突。<br>JDK8之前，这种方法被称为链地址法，因为使用链表存储同一桶内的元素。通常情况HashMap，HashSet，LinkedHashSet，LinkedHashMap，ConcurrentHashMap，HashTable，IdentityHashMap和WeakHashMap均采用这种方法处理冲突。<br>从JDK 8开始，HashMap，LinkedHashMap和ConcurrentHashMap为了提升性能，在频繁冲突的时候使用平衡树来替代链表。因为HashSet内部使用了HashMap，LinkedHashSet内部使用了LinkedHashMap，所以他们的性能也会得到提升。</p>

                <hr>
                

                <ul class="pager">
                    
                    <li class="previous">
                        <a href="/2017/07/11/如何安全的使用HashMap/" data-toggle="tooltip" data-placement="top"
                           title="如何安全的使用HashMap">&larr; Previous Post</a>
                    </li>
                    
                    
                    <li class="next">
                        <a href="/2017/07/08/Hexo + 码云搭建个人博客/" data-toggle="tooltip" data-placement="top"
                           title="Hexo + 码云搭建个人博客">Next Post &rarr;</a>
                    </li>
                    
                </ul>

                

                


                <!--加入新的评论系统-->
                
            </div>

            <div class="hidden-xs col-sm-3 toc-col">
                <div class="toc-wrap">
                    <ol class="toc"><li class="toc-item toc-level-4"><a class="toc-link" href="#什么时候会产生冲突"><span class="toc-text">什么时候会产生冲突</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#总结"><span class="toc-text">总结</span></a>
                </div>
            </div>
        </div>

        <div class="row">
            <!-- Sidebar Container -->

            <div class="
                col-lg-8 col-lg-offset-2
                col-md-10 col-md-offset-1
                sidebar-container">

                <!-- Featured Tags -->
                
                <section>
                    <!-- no hr -->
                    <h5 class="text-center">
                        <a href="/tags/">FEATURED TAGS</a>
                    </h5>
                    <div class="tags">
                        
                        <a class="tag" href="/tags/#个人学习"
                           title="个人学习">个人学习</a>
                        
                    </div>
                </section>
                

                <!-- Friends Blog -->
                
            </div>
        </div>

    </div>
</article>







<!-- Footer -->
<!-- Footer -->
<footer>
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1 text-center">
                <br>
                <ul class="list-inline text-center">
                
                
                

                

                

                

                

                </ul>
                <p class="copyright text-muted">
                    Copyright &copy; 菜菜莱莱 2017
                    <br>
                    <span id="busuanzi_container_site_pv" style="font-size: 12px;">PV: <span id="busuanzi_value_site_pv"></span> Times</span>
                    <br>
                    Theme by <a href="https://haojen.github.io/">Haojen Ma</a>
                </p>

            </div>
        </div>
    </div>
</footer>

<!-- jQuery -->
<script src="/js/jquery.min.js"></script>

<!-- Bootstrap Core JavaScript -->
<script src="/js/bootstrap.min.js"></script>

<!-- Custom Theme JavaScript -->
<script src="/js/blog.js"></script>

<!-- async load function -->
<script>
    function async(u, c) {
      var d = document, t = 'script',
          o = d.createElement(t),
          s = d.getElementsByTagName(t)[0];
      o.src = u;
      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
      s.parentNode.insertBefore(o, s);
    }
</script>

<!-- jquery.tagcloud.js -->
<script>
    // only load tagcloud.js in tag.html
    if($('#tag_cloud').length !== 0){
        async("http://sy0626.gitee.io/js/jquery.tagcloud.js",function(){
            $.fn.tagcloud.defaults = {
                //size: {start: 1, end: 1, unit: 'em'},
                color: {start: '#bbbbee', end: '#0085a1'},
            };
            $('#tag_cloud a').tagcloud();
        })
    }
</script>

<!--fastClick.js -->
<script>
    async("//cdn.bootcss.com/fastclick/1.0.6/fastclick.min.js", function(){
        var $nav = document.querySelector("nav");
        if($nav) FastClick.attach($nav);
    })
</script>

<!-- Google Analytics -->



<!-- Baidu Tongji -->


<!-- swiftype -->
<script type="text/javascript">
  (function(w,d,t,u,n,s,e){w['SwiftypeObject']=n;w[n]=w[n]||function(){
  (w[n].q=w[n].q||[]).push(arguments);};s=d.createElement(t);
  e=d.getElementsByTagName(t)[0];s.async=1;s.src=u;e.parentNode.insertBefore(s,e);
  })(window,document,'script','//s.swiftypecdn.com/install/v2/st.js','_st');

  _st('install','','2.0.0');
</script>

<script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<!--wechat title img-->
<img class="wechat-title-img" src="">
</body>

</html>
